/*
 * 4.5
 * Write an algorithm to find the ‘next’ node (i.e., in-order successor) of a given node in
 * a binary search tree where each node has a link to its parent.
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct _tree_t {
    int value;
    struct _tree_t *left;
    struct _tree_t *right;
    struct _tree_t *parent;
} tree_t;

tree_t *new_tree(int v)
{
    tree_t *t = (tree_t *)malloc(sizeof(tree_t));
    memset(t, 0, sizeof(tree_t));
    t->value = v;
    return t;
}

tree_t *inorder_next(tree_t *t)
{
    if (t->right) {
        tree_t *next = t->right;
        while (next->left) {
            next = next->left;
        }
        return next;
    } else { // XXX: the else branch was not considered :(
        tree_t *parent = t->parent;
        if (!parent) {
            return NULL;
        }
        if (parent->left == t) {
            return parent;
        } else {
            tree_t *p;
            while ((p = parent->parent)) {
                if (p->left == parent) {
                    break;
                }
                parent = p;
            }
            return p;
        }
    }
}

void free_tree(tree_t *root)
{
    if (!root) {
        return;
    }
    free_tree(root->left);
    free_tree(root->right);
    free(root);
}

int main()
{
    tree_t *nodes[7];
    for (int i = 0; i < 7; i++) {
        nodes[i] = new_tree(i);
    }
    tree_t *root = nodes[0];
    root->left = nodes[1];
    root->right = nodes[2];
    nodes[1]->parent = root;
    nodes[2]->parent = root;
    nodes[1]->left = nodes[3];
    nodes[1]->right = nodes[4];
    nodes[3]->parent = nodes[1];
    nodes[4]->parent = nodes[1];
    nodes[4]->left = nodes[5];
    nodes[4]->right = nodes[6];
    nodes[5]->parent = nodes[4];
    nodes[6]->parent = nodes[4];
    tree_t *t = inorder_next(nodes[5]);
    printf("inorder_next of 5 is: %d\n", t ? t->value : -1);
    t = inorder_next(nodes[2]);
    printf("inorder_next of 2 is: %d\n", t ? t->value : -1);
    free_tree(root);
    return 0;
}
